leetcode 795 区间子数组的个数

想岔了，开始还以为很难，后来想通了。

题目

给定一个元素都是正整数的数组A ，正整数 L 以及 R (L <= R)。

求连续、非空且其中最大元素满足大于等于L 小于等于R的子数组个数。

例如 :
输入:
A = [2, 1, 4, 3]
L = 2
R = 3
输出: 3
解释: 满足条件的子数组: [2], [2, 1], [3].

思路

因为要满足的是最大值大于等于R小于等于L，那首先找到所有的最大值小于等于R的子数组的个数，然后现在这些子数组里面肯定包含了最大值小于L的子数组（如果存在，因为R>=L）,那用同样的方法找到最大值小于L的子数组的个数，然后相减就是结果了。一个长度为N的数组，它的连续子数组的个数是（N+1)*N/2。

code

int numSubarrayBoundedMax(vector<int>& A, int L, int R) 
{
    int num1=0;
    int num2=0;
    for(int i=0,j=0;i<A.size();)
    {
        if(A[i]<=R)//记录下所有的满足最大值小于等于R的子数组的个数，但是其中包含最小值小于L的子数组
        {//这里相当于加上了当前长度N，因为之前说的，长度为N的数组连续子数组的个数为1+2+3+..N
            num1+=(++i)-j;
        }
        else
        {//如果当前元素不满足小于等于R，那么跳过该元素，继续寻找。
            j=++i;
        }
    }
    for(int i=0,j=0;i<A.size();)
    {
        if(A[i]<L)//找出最大值小于L的子数组的个数，小于L，那么肯定小于R，所以两者相减就是答案。
        {
            num2+=(++i)-j;
        }
        else
        {
            j=++i;
        }
    }
    return num1-num2;

}